package recursion

import problem.Problem

class Q206ReverseLinkedList extends Problem {
  def reverseList(head: ListNode): ListNode = {
    if (head == null) head
    else {
      val (_, tail) = reverse(head)
      head.next = null
      tail
    }
  }

  def reverse(node: ListNode): (ListNode, ListNode) = {
    // println(s"${node}")
    if (node.next == null) (node, node)
    else {
      val (next, last) = reverse(node.next)
      next.next = node
      (node, last)
    }
  }

  override def test(): Unit = {
    val head = nodes(5)
    println(head)
    println(reverseList(head))
  }
}